package LeetCode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class LC_407_TrappingRainWaterII {

    public static void main(String[] args) {

    }

    public class Solution {
        public int trapRainWater(int[][] heightMap) {
            if (heightMap.length == 0 || heightMap[0].length == 0) return 0;
            int m = heightMap.length, n = heightMap[0].length;
            boolean[][] visited = new boolean[m][n];
            PriorityQueue<Cell> minHeap = new PriorityQueue<>((m + n), Comparator.comparingInt(a -> a.h));
            for (int i = 0; i < m; i++) {
                minHeap.offer(new Cell(i, 0, heightMap[i][0]));
                visited[i][0] = true;
                minHeap.offer(new Cell(i, n - 1, heightMap[i][n - 1]));
                visited[i][n - 1] = true;
            }
            for (int j = 0; j < n; j++) {
                minHeap.offer(new Cell(0, j, heightMap[0][j]));
                visited[0][j] = true;
                minHeap.offer(new Cell(m - 1, j, heightMap[m - 1][j]));
                visited[m - 1][j] = true;
            }
            int res = 0;
            while (!minHeap.isEmpty()) {
                Cell cur = minHeap.poll();
                for (int[] dir : dirs) {
                    int nx = cur.x + dir[0], ny = cur.y + dir[1];
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                        visited[nx][ny] = true;
                        if (heightMap[nx][ny] < cur.h) res += cur.h - heightMap[nx][ny];
                        minHeap.offer(new Cell(nx, ny, Math.max(cur.h, heightMap[nx][ny])));
                    }
                }
            }
            return res;
        }

        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    }

    class Cell {
        int x;
        int y;
        int h;

        Cell(int x, int y, int h) {
            this.x = x;
            this.y = y;
            this.h = h;
        }
    }

}